package subject_set.interview.Day3_23_yunzi;

import java.util.Scanner;

/**
 * @author haomin
 * @date 2023/03/23 16:07
 **/
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
//        System.out.println("第" + n + "个斐波那契数是： " + getFib(n));
        System.out.println("第" + n + "个斐波那契数是： " + getFib2(n));
    }

    // 0,1,1,2, 3, 5, 8, 13
    private static int getFib(int n) {
        if(n <= 1) return n == 0 ? 0 : 1;
        int[] dp = new int[n+1];
        dp[0] = 0; dp[1] = 1;
        for(int i = 2; i <= n; ++i) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return  dp[n];
    }

    private static int getFib2(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;

        return getFib2(n - 1) + getFib2(n - 2);
    }

    // 冒泡排序、选择排序、直接插入排序、希尔排序、快速排序、堆排序
}